##def rek(parent, childs, length=5, depth=0):
##
##    #print " " * depth, "zip: ", zip(childs, childs[1:] + [length])
##    if not length in childs:
##        print parent, childs
##        for i, j in zip(childs, childs[1:] + [length]):
##            for r in range(i + 1, j):
##                #print " " * depth, childs, ": i: %s, j: %s, r: %s" % (i, j, r)
##                c = list(childs)
##                c[childs.index(i)] = r
##                return_childs = [childs]
##                return_childs = return_childs + rek(parent, c, length, depth + 2)
##                return return_childs
##
##        #rek(one, two, three + 1)
##    return [childs]
##    #yield one, two, three

#foo = rek(0,[1,2], 5)
#print foo


#==== ==== ==== ====
# SMITRAN v 1.0
#==== ==== ==== ====
# s = ngrami dolzine k
# v t pa iscemo vse te ngrame na ssk nacin (s preskoki)
# na vsakega vrne stand. odklon
def smitran_kernel(s1, s2, data):
    ngrams = data[s1][0]
    charIndexes = data[s2][1]

    suma = 0
    for ngram in ngrams:
        stringIndexes = [charIndexes.get(i, []) for i in ngram]
        sskFind = sskFindOut()
        sskFind(-1, stringIndexes)

        for i in sskFind(True):
            smit = i / float(k)
            calc_smit = decay ** smit
            suma = suma + calc_smit

    #print suma
    return suma


def ngram_kernel_old(s1, s2, data, k=0, decay=0):
    '''simple n-gram string kernel'''
    kmers1 = data[s1]
    kmers2 = data[s2]
    inter = set(kmers1).intersection(kmers2)

    # run 100 = 0.167 CPU seconds! very nice
    s1d = dict([(i, 0) for i in kmers1])
    s2d = dict([(i, 0) for i in kmers2])

    for i in kmers1:
        s1d[i] += 1

    for i in kmers2:
        s2d[i] += 1

    return sum(s1d[i] * s2d[i] for i in inter)





# 100x = 2.798 CPU seconds
def smitran_kernel(s1, s2, data, k, decay, order, smitran):
    charIndexes1 = data[s1][1]
    charIndexes2 = data[s2][1]

    kmers1 = data[s1][0]
    kmers2 = data[s2][0]
    #inter = set(kmers1).intersection(kmers2)
    allNgram = set(kmers1).intersection(kmers2)  #set(append(kmers1, kmers2))

    produkt = 0.0
    for ngram in allNgram:
        # Dobi indexe crk iz ngrama
        # dict .get 1.000.000x = 2.514 CPU seconds
        # dict [a]  1.000.000x = 0.350 CPU seconds!!!
        stringIndexes1 = [charIndexes1.get(i, []) for i in ngram]
        stringIndexes2 = [charIndexes2.get(i, []) for i in ngram]

        sskFind1 = sskFindOut(k, order, stringIndexes1)
        sskFind1(-1, 0)

        sskFind2 = sskFindOut(k, order, stringIndexes2)
        sskFind2(-1, 0)

        odklon1 = sum([decay ** (odklon ** smitran) for odklon in sskFind1(-99)]) #sum(decay ** sskFind1(True))
        odklon2 = sum([decay ** (odklon ** smitran) for odklon in sskFind2(-99)])

        produkt += odklon1 * odklon2

    #print suma
    return produkt